package 力扣_树算法.遍历.层序遍历扩展;


import java.util.ArrayDeque;
import java.util.Deque;

/**513. 找树左下角的值
 * @author zx
 * @create 2022-04-12 11:58
 */
public class 找树左下角的值_513 {
    /**
     层序遍历,只要将每一层的第一个节点赋值到left,那么最后一层的left一定为最后一层的最左节点。
     */
    public int findBottomLeftValue2(TreeNode root) {
        int res = 0;
        if(root == null){
            return 0;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            res = queue.peekFirst().val;
            for(int i = 0;i < size;i++){
                TreeNode node = queue.poll();
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }

    /**
     判断当前深度curDepth是否为大于最大深度maxDepth,若大于,则将当前的节点值赋给left,同时更新最大深度的值。
     此做法可以保证,当遇到当前深度大于最大深度时,赋值给left的值一定是这一层最左边的节点值,因为后面的都是同一层
     不满足大于条件。若是判断大于等于,则left将被赋为这一层的最右节点的值。
     */
    int left = 0;
    int maxDepth = 0;
    public int findBottomLeftValue(TreeNode root) {
        depth(root, 1);
        return left;
    }

    public void depth(TreeNode root, int curDepth) {
        if(root == null)
            return;
        left = curDepth > maxDepth ? root.val : left;
        maxDepth = Math.max(curDepth, maxDepth);
        depth(root.left, curDepth + 1);
        depth(root.right, curDepth + 1);
    }
}
